package algotithm.leetcode.dp.test403;

/**
 * @author 25068
 * @Date 2021/4/29 8:46
 * @Title 403. 青蛙过河
 */
public class Solution {

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] stones = {0,1,3,5,6,8,12,17};
        boolean b = s.canCross(stones);
        System.out.println(b);
    }

    public boolean canCross(int[] stones) {
        int n = stones.length;
        boolean[][] dp = new boolean[n][n + 1];
        dp[0][0] = true;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int k = stones[i] - stones[j];
                if (k <= j + 1) {
                    dp[i][k] = dp[j][ k - 1] || dp[j][k] || dp[j][ k + 1];
                    if (i == n - 1 && dp[i][k]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

}
